package algorithm

// 二分排序
func BinaryInsertionSort(arr []int) {
	for i := 1; i < len(arr); i++ {
		key := arr[i]
		low := 0
		high := i - 1

		// 使用二分查找找到插入位置
		for low <= high {
			mid := (low + high) / 2

			if arr[mid] > key {
				high = mid - 1
			} else {
				low = mid + 1
			}
		}

		// 将元素插入到正确的位置
		for j := i - 1; j >= low; j-- {
			arr[j+1] = arr[j]
		}
		arr[low] = key
	}
}

// 快排
func QuickSort(arr []int) []int {
	if len(arr) <= 1 {
		return arr
	}

	pivot := arr[0]
	left := make([]int, 0)
	right := make([]int, 0)

	for _, num := range arr[1:] {
		if num < pivot {
			left = append(left, num)
		} else {
			right = append(right, num)
		}
	}

	left = QuickSort(left)
	right = QuickSort(right)

	return append(append(left, pivot), right...)
}
